Finite field arithmetic operations, which use the remainder of an arithmetic result between integers, have been used for basic techniques which are applicable to various fields such as error correction codes (ECC) and cryptography. Partly due to the wide application field, a number of studies have been conducted in order to make the circuits performing multiplications and modular arithmetic operations faster, be implemented in a smaller size, and consume less power. A modular multiplication is an operation of calculating the remainder when dividing the multiplication result of integers by another integer. For example, a Montgomery multiplication is known as an algorithm which can execute the modular multiplication at a high speed.
When using the Montgomery multiplication, numbers on a finite field subject to an arithmetic operation are mapped in advance to numbers on the Montgomery space, and then the Montgomery multiplication is performed. The result of the Montgomery multiplication is mapped back to the numbers on the finite field. In this way, it is possible to obtain the result which originally is to be obtained. Since the Montgomery multiplication requires conversion and inverse conversion, the use of the Montgomery multiplication for a single modular multiplication incurs a large cost, but the Montgomery multiplication is well-suited to a case when successively performing the modular multiplication several times as in a modular exponentiation operation.
There are mainly two implementation methods for the Montgomery multiplication. The first implementation method uses word multipliers. When one word is made up of 32 bits, for example, this method uses 32-bit multipliers capable of calculating a 64-bit product which is the multiplication result of 32 bits by 32 bits. In this case, it is known that (2×M^2+M) multiplications are required if the number of words of the modulus is M. If there is one multiplier, a single Montgomery multiplication requires (2×M^2+M) clocks.
The other implementation method uses adders of a large number of digits. This method uses adders capable of calculating the addition result of 1024 bits+1024 bits if the modulus is made up of 1024 bits. (2×m) additions are required if the number of bits of the modulus is m. If there is one adder, a single Montgomery multiplication requires (2×m) clocks.
For example, when a word-based Montgomery multiplication uses 32×32-bit multipliers, and the modulus is made up of 1024 bits, M=32 words, and therefore, 2080 clocks are required. On the other hand, in the Montgomery multiplication using adders, when the modulus is made up of 1024 bits, 2048 clocks are required. When the modulus is made up of 2048 bits, M=64 words, and therefore, 8256 clocks are required in the word-based Montgomery multiplication, while 4096 clocks are required in the Montgomery multiplication using adders.
Moreover, as a method of accelerating multiplications, there is a known method of using a redundant binary representation such as a Non-Adjacent Form (NAF; see D. Hankerson, A. Menezes, S. Vanstone, “Guide to Elliptic Curve Cryptography,” Springer, 2004, p. 98.). This method accelerates multiplications taking advantage of the fact that the average number of zeros included increases when a multiplier is represented in a redundant binary representation.
Furthermore, as a method for accelerating modular multiplications as well as multiplications using a redundant binary representation, a ZDN method is known (for example, see H. Sedlak, “The RSA cryptography processor,” Proceedings of EUROCRYPT '87 (Amsterdam) (D. Chaum and W. L. Price, eds.), LNCS, vol. 304, Springer-Verlag, Berlin, 1988, pp. 95-105). In the ZDN method, when the number of bits of the modulus is m, ideally, it is possible to calculate a modular multiplication with m/3 clocks (steps). For example, when the number of bits of the modulus is 1024, ideally, it is possible to calculate a modular multiplication with 342 steps.
However, the ZDN method is a method which performs the arithmetic process sequentially from the significant bit. That is, the ZDN method is a left-to-right process (L-R process). In general, in the case of the L-R process, there is a problem in that it is difficult to change the number of processing bits. For example, the position of the most significant bit changes between when processing 1024 bits and when processing 512 bits. As a result, there is a problem in that a plurality of circuits are required so as to correspond to the bit position from which the process starts. Therefore, in order to implement the ZDN method under the present circumstances, it may be a practical solution to fix the number of processing bits. Since the ZDN method is an algorithm which processes from the most significant bit, there is a problem in that it is difficult to freely change the number of processing bits.
On the other hand, as described above, the Montgomery multiplication of the related art requires 2×M^2+M clocks or 2×m clocks and has a problem associated with its processing speed which is slower than the ZDN method.